package primalgorithms.array;

import java.util.Arrays;
import java.util.HashMap;

public class _06Intersect {
    public static int[] intersect(int[] nums1, int[] nums2) {
        /**
         * 该算法有问题，会重复添加冗余元素
        int len1=nums1.length,len2=nums2.length;
        if(len1 == 0 || len2 == 0){
            return null;
        }
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0;i < len1;i++){
            for (int j = 0;j < len2;j++){
                if(nums1[i] == nums2[j]){
                    arr.add(nums1[i]);
                }
            }
        }
        int[] res = new int[arr.size()];
        int i = 0;
        for (Integer num : arr){
            res[i] = arr.get(i);
            i++;
        }
        return res;
        */
        //重点：哈希表计数法
        //对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值
        //由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数
        int len1=nums1.length,len2=nums2.length;
        if(len1 == 0 || len2 == 0){
            return null;
        }
        HashMap<Integer,Integer> intNum = new HashMap<>();
        //先遍历一遍第一个数组，记录进哈希表中
        for (int i = 0;i < len1;i++){
            /**
             * getOrDefault(key,default),default：默认值
             * 作用：如果存在相应的key则返回其对应的value，否则返回给定的默认值
             * 所以这里返回值类型就是Integer
             * */
            intNum.put(nums1[i],intNum.getOrDefault(nums1[i],0)+1);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        //遍历第二个数组
        for (int i = 0;i < len2;i++){
            //先检查哈希表中是否存在nums2中的元素
            //这里用一个巧妙的方法
            //count计数器，如果count==0，则还没有该元素
            int count = intNum.getOrDefault(nums2[i],0);
            if(count > 0){
                intersection[index++] = nums2[i];
                //注意：添加新元素后需要将计数器的值-1
                count--;
                //相应元素的value值减少1
                if(count > 0){
                    intNum.put(nums2[i],count);
                }else {
                    intNum.remove(nums2[i]);
                }
            }
        }
        //重要方法：copyOfRange
        //取值范围依然是左闭右开
            return Arrays.copyOfRange(intersection,0,index);
    }
}
